package com.example.demo.suanfa;

import java.util.*;

public class chuji {


/**
 * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
 *
 * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
 *
 */
    public void reverseString(char[] s) {
        int left =0;
        int right = s.length-1;
        while (left<right){
            char temp =s[left];
            s[left]=s[right];
            s[right]=temp;
            left=left+1;
            right=right-1;
        }
    }
    /**
     * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
     *
     * 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
     *
     * 将最终结果插入 nums 的前 k 个位置后返回 k 。
     *
     * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public static int removeDuplicates(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int index=1;
        int count=1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==nums[index-1]){
                continue;
            }
            nums[index]=nums[i];
            index++;
            count++;
            System.out.println(Arrays.toString(nums));
        }
        return count;
    }


    /**
     * 给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
     *
     * 在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static int maxProfit(int[] prices) {
        if(prices==null||prices.length==0){
            return  0;
        }
        int max =0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]){
                max=max+(prices[i]-prices[i-1]);
            }
        }
        return max;
    }

    /**
     * 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *
     * 输入：nums = [-1,-100,3,99], k = 2
     * 输出：[3,99,-1,-100]
     * 解释:
     * 向右轮转 1 步: [99,-1,-100,3]
     * 向右轮转 2 步: [3,99,-1,-100]
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
        public static void rotate(int[] nums, int k) {
            if(k==0){
                return;
            }
            int [] temp=new int[nums.length];
            int sise=nums.length;
            for (int i=0;i<sise;i++){
                if(i+k<sise){
                    temp[i+k]=nums[i];
                }else{
                    temp[(i+k)%sise]=nums[i];
                }
            }
            for (int i=0;i<sise;i++){
                nums[i]=temp[i];
            }
            System.out.println(Arrays.toString(nums));
        }


    /**
     * 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
     *输入：nums = [1,2,3,4]
     * 输出：false
     */

    public boolean containsDuplicate(int[] nums) {
        if(nums==null||nums.length==0){
            return false;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if(!set.add(nums[i])){
                return true;
            }
        }
        return false;
    }

    public boolean containsDuplicate1(int[] nums) {
        if(nums==null||nums.length==0){
            return false;
        }
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if(nums[i-1]==nums[i]){
                return true;
            }
        }
        return false;
    }
    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 输入: [2,2,1]
     * 输出: 1
     */
    public  static int singleNumber(int[] nums) {
        int val=0;
         for (int num:nums){
             val=val^num;
         }
         return val;
    }
    /**
     * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> result= new ArrayList<>();
        int index1 =0;
        int index2=0;
        while (index1<nums1.length&&index2<nums2.length){
            if(nums1[index1]==nums2[index2]){
                result.add(nums1[index1]);
                index1++;
                index2++;
            }else if(nums1[index1]<nums2[index2]){
                index1++;
            }else{
                index2++;
            }
        }
        Integer [] rel = new Integer[result.size()];
        Integer[] integers = result.toArray(rel);
        int[] ints = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();
        return ints;
    }

    /**
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     *
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     *
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param digits
     * @return
     */

    public static int[] plusOne(int[] digits) {
        int length =digits.length;
        //记录需要加一的位置
        int isPlusIndex=0;
        for (int i = length-1; i >=0 ; i--) {
            if(digits[i]==9 &&i==length-1){
                digits[i]=0;
                isPlusIndex=i-1;
                if(i==0){
                    return new int[]{1,0};
                }
            }else if(digits[i]==9){
                if(isPlusIndex!=0){
                    digits[isPlusIndex]=0;
                    isPlusIndex=isPlusIndex-1;
                }
                if(i==0){
                    int[] digitsNew = new int[digits.length+1];
                    for (int j = 0; j < digitsNew.length; j++) {
                        if(j==0){
                            digitsNew[0]=1;
                        }else{
                            digitsNew[j]=0;
                        }
                    }
                    return digitsNew;
                }
            }else{
                digits[i]=digits[i]+1;
                return digits;
            }
        }
        return digits;
    }

    public static int[] plusOne1(int[] digits) {
        int length = digits.length;
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                //如果数组当前元素不等于9，直接加1
                //然后直接返回
                digits[i]++;
                return digits;
            } else {
                //如果数组当前元素等于9，那么加1之后
                //肯定会变为0，我们先让他变为0
                digits[i] = 0;
            }
        }
        //除非数组中的元素都是9，否则不会走到这一步，
        //如果数组的元素都是9，我们只需要把数组的长度
        //增加1，并且把数组的第一个元素置为1即可
        int temp[] = new int[length + 1];
        temp[0] = 1;
        return temp;
    }

    /**
     *
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        if(nums==null||nums.length==0){
            return;
        }
        int index=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[index]=nums[i];
                index++;
            }
        }
        while (index<nums.length){
            nums[index]=0;
            index++;
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * @param
     */

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <nums.length ; j++) {
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
            
        }
        return null;
    }
    public static int[] twoSum1(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(target-nums[i])!=null){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
return null;
    }

public static boolean isValisudoku1(char board[][]){
    int length=board.length;
    int [][] row = new int[length][length];
    int [][] col = new int[length][length];
    int [][] bock = new int[length][length];
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            if(board[i][j]=='.'){
                continue;
            }
            int num =board[i][j]-'0'-1;
            int k=i/3*3+j/3;
            if(row[i][num]!=0||col[j][num]!=0||bock[k][num]!=0){
                return false;
            }
            row[i][num]=col[j][num]=bock[k][num]=1;
        }
    }
    return true;
}





    public static boolean isValidSudoku(char board[][]) {
        int length = board.length;
        //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
        //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
        int line[][] = new int[length][length];
        int column[][] = new int[length][length];
        int cell[][] = new int[length][length];
        for (int i = 0; i < length; ++i)
            for (int j = 0; j < length; ++j) {
                //如果还没有填数字，直接跳过
                if (board[i][j] == '.')
                    continue;
                //num是当前格子的数字
                int num = board[i][j] - '0' - 1;
                //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
                int k = i / 3 * 3 + j / 3;
                System.out.println("k-->"+k);
                //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
                //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
                if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
                    return false;
                //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
                line[i][num] = column[j][num] = cell[k][num] = 1;
            }
        return true;
    }



    public static void rotate1(int[][] matrix) {
        int length = matrix.length;
        for (int i = 0; i < length/2; i++) {
            for (int j=i;j<length-i-1;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[length-j-1][i];
                matrix[length-j-1][i]=matrix[length-i-1][length-j-1];
                matrix[length-i-1][length-j-1]=matrix[j][length-i-1];
                matrix[j][length-i-1]=temp;
            }
        }
    }


















    public static void rotate(int[][] matrix) {
        int length = matrix.length;
        //因为是对称的，只需要计算循环前半行即可
        for (int i = 0; i < length / 2; i++){
            System.out.println("i->"+i);
            for (int j = i; j < length - i - 1; j++) {
                System.out.println(j);
                int temp = matrix[i][j];
                System.out.println("tmp->"+temp);
                int m = length - j - 1;
                int n = length - i - 1;
                matrix[i][j] = matrix[m][i];
                matrix[m][i] = matrix[n][m];
                matrix[n][m] = matrix[j][n];
                matrix[j][n] = temp;
            }
        }
        System.out.println("1");
    }



    public static void main(String[] args) {
//       int  matrix [][]= {{5,1,9,11}, {2,4,8,10}, {13,3,6,7}, {15,14,12,16}};

//        rotate(matrix);


//        char board[][]=     {{'5','3','.','.','7','.','.','.','.'}
//,{'6','.','.','1','9','5','.','.','.'}
//,{'.','9','8','.','.','.','.','6','.'}
//,{'8','.','.','.','6','.','.','.','3'}
//,{'4','.','.','8','.','3','.','.','1'}
//,{'7','.','.','.','2','.','.','.','6'}
//,{'.','6','.','.','.','.','2','8','.'}
//,{'.','.','.','4','1','9','.','.','5'}
//,{'.','.','.','.','8','.','.','7','9'}};
//
//        isValidSudoku(board);

//        System.out.println(3/3*3);



//        int []aa={1,2,3,7,5};
//        int []bb={1,22,22,2323,232};
//        removeDuplicates(aa);
//        System.out.println(maxProfit(aa));
//        rotate(aa,3);
//        intersect(aa,bb);
//        System.out.println(singleNumber(aa));
//         moveZeroes(aa);
//        int[] ints = twoSum1(aa, 5);
//        System.out.println(Arrays.toString(ints));

    }
}
